package gold.digger;

import gold.utils.InputUtil;

import java.util.*;

/**
 * Created by fanzhenyu02 on 2021/12/10.
 * common problem solver template.
 */
public class LC514 {
    public long startExecuteTime = System.currentTimeMillis();


    class Solution {

        Map<String, Integer> memo = new HashMap<>();

        public int findRotateSteps(String ring, String key) {
            Map<Character, List<Integer>> charPosMap = new HashMap<>();
            for (int i = 0; i < ring.length(); i++) {
                if (!charPosMap.containsKey(ring.charAt(i))) charPosMap.put(ring.charAt(i), new ArrayList<>());
                charPosMap.get(ring.charAt(i)).add(i);
            }

            return dfs(ring, key, 0, 0, charPosMap);
        }

        public int dfs(String ring, String key, int ringPos, int keyPos, Map<Character, List<Integer>> charPosMap) {
            if (keyPos >= key.length()) return 0;
            String curKey = ringPos + "_" + keyPos;
            if (memo.containsKey(curKey)) return memo.get(curKey);

            int curMinStep = Integer.MAX_VALUE;
            char curNeed = key.charAt(keyPos);
            List<Integer> curNeedPosList = charPosMap.get(curNeed);
            for (Integer ringNextPos : curNeedPosList) {
                int curStep = Math.min(Math.abs(ringNextPos - ringPos), ring.length() - Math.abs(ringNextPos - ringPos)) + 1;
                curStep += dfs(ring, key, ringNextPos, keyPos + 1, charPosMap);
                curMinStep = Math.min(curMinStep, curStep);
            }

            memo.put(curKey, curMinStep);
            return curMinStep;
        }
    }

    public void run() {
//        System.out.println(new Solution().findRotateSteps("godding", "gd"));
//        System.out.println(new Solution().findRotateSteps("godding", "godding"));
        System.out.println(new Solution().findRotateSteps("pqwcx", "cpqwx"));
    }

    public static void main(String[] args) throws Exception {
        LC514 an = new LC514();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
